package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked
 * 思路1：求最大值，可以看成求被0拆分的各个子数组的最大值。
 * 当一个数组中没有0存在，则分为两种情况：
 * <p>
 * 1.负数为偶数个，则整个数组的各个值相乘为最大值；
 * <p>
 * 2.负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，从右边也有一个“最大值”，比较，得出最大值。
 * <p>
 * <p>
 * 思路2：动态规划
 *
 * @author yulongtian
 * @create 2024-07-23 15:49
 */
public class Test84 {
    public static void main(String[] args) {

    }

    /*
    思路2：动态规划
     */
    public int maxProduct(int[] nums) {
        double maxF = nums[0];
        double minF = nums[0];
        double ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            double mx = maxF;
            double mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i]));
            minF = Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i]));
            ans = Math.max(ans, maxF);
        }
        return (int) ans;
    }


//    /*
//    思路1方法
//     */
//    public int maxProduct(int[] nums) {
//        int n = nums.length;
//        double a = 1.0;
//        double max = nums[0];
//        for (int num : nums) {
//            a = a * num;
//            if (max < a) max = a;
//            if (num == 0) a = 1;
//        }
//        a = 1;
//        for (int i = n - 1; i >= 0; i--) {
//            a = a * nums[i];
//            if (max < a) max = a;
//            if (nums[i] == 0) a = 1;
//        }
//        return (int) max;
//    }
}
